#pragma once

#define CUSTOM_STRING_VIEW 1

#if __cplusplus >= 201703L
#   if defined(__has_include)
#       if __has_include(<string_view>)
#           undef CUSTOM_STRING_VIEW
#           include <string_view>
#       elif __has_include(<experimental/string_view>)
#           undef CUSTOM_STRING_VIEW
#           include <experimental/string_view>
			namespace std {
				using string_view = experimental::string_view;
			}
#       endif
#   endif
#endif

#ifdef CUSTOM_STRING_VIEW

#include <endian.h>

#include <string>
#include <stdexcept>
#include <cstring>

namespace std {

    class string_view {
    public:
        using size_type = std::size_t ;

        static constexpr size_type npos = size_type(-1);

        constexpr string_view() noexcept: data_(nullptr), size_(0) { }

        constexpr string_view(const string_view& other) noexcept = default;

        constexpr string_view(const char *s, size_type count) : data_(s), size_(count) { }

        string_view(const char *s) : data_(s), size_(strlen(s)) { }


        string_view
        substr(size_type pos, size_type count = npos) const {
            if (pos > size_) {
                throw std::out_of_range("Out of range.");
            }
            size_type rcount = std::min(count, size_ - pos);
            return {data_ + pos, rcount};
        }

        constexpr size_type
        size() const noexcept {
            return size_;
        }

        constexpr size_type
        length() const noexcept {
            return size_;
        }


        constexpr char operator[](size_type pos) const {
            return data_[pos];
        }

        constexpr const char *data() const noexcept {
            return data_;
        }

        bool
        operator==(const string_view &rhs) const {
            return (!std::lexicographical_compare(data_, data_ + size_, rhs.data_, rhs.data_ + rhs.size_) &&
                    !std::lexicographical_compare(rhs.data_, rhs.data_ + rhs.size_, data_, data_ + size_));
        }

        string_view &
        operator=(const string_view &view) noexcept = default;

        size_type find(string_view v, size_type pos = 0) const noexcept {
            if (size_ < pos)
                return npos;

            if ((size_ - pos) < v.size_)
                return npos;

            for (; pos <= (size_ - v.size_); ++pos) {
                bool found = true;
                for (size_type i = 0; i < v.size_; ++i) {
                    if (data_[pos + i] != v.data_[i]) {
                        found = false;
                        break;
                    }
                }
                if (found) {
                    return pos;
                }
            }

            return npos;
        }

        size_type find(char ch, size_type pos = 0) const noexcept {
            return find(string_view(&ch, 1), pos);
        }

        size_type find(const char *s, size_type pos, size_type count) const {
            return find(string_view(s, count), pos);
        }

        size_type find(const char *s, size_type pos = 0) const {
            return find(string_view(s), pos);
        }

        size_type rfind(string_view v, size_type pos = npos) const noexcept {
            if (v.size_ > size_)
                return npos;

            if (pos > size_)
                pos = size_;
            size_t start = size_ - v.size_;
            if (pos != npos)
                start = pos;
            for (size_t offset = 0; offset <= pos; ++offset, --start) {
                bool found = true;
                for (size_t j = 0; j < v.size_; ++j) {
                    if (data_[start + j] != v.data_[j]) {
                        found = false;
                        break;
                    }
                }
                if (found) {
                    return start;
                }
            }

            return npos;
        }

        size_type rfind(char c, size_type pos = npos) const noexcept {
            return rfind(string_view(&c, 1), pos);
        }

        size_type rfind(const char* s, size_type pos, size_type count) const {
            return rfind(string_view(s, count), pos);
        }

        size_type rfind(const char* s, size_type pos = npos) const {
            return rfind(string_view(s), pos);
        }

        constexpr bool empty() const noexcept {
            return size_ == 0;
        }
    private:
      const char *data_;
      size_type size_;
    };

    template<>
    struct hash<string_view> {
    //-----------------------------------------------------------------------------
    // MurmurHash3 was written by Austin Appleby, and is placed in the public
    // domain. The author hereby disclaims copyright to this source code.
    private:
#ifdef __GNUC__
#define FORCE_INLINE __attribute__((always_inline)) inline
#else
#define FORCE_INLINE inline
#endif

        static FORCE_INLINE std::uint32_t Rotl32(const std::uint32_t x,
                                                 const std::int8_t r) {
            return (x << r) | (x >> (32 - r));
        }

        static FORCE_INLINE std::uint32_t Getblock(const std::uint32_t *p,
                                                   const int i) {
#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
            return p[i];
#else
            std::uint32_t temp_number = p[i];
            uint8_t (&number)[4] = *reinterpret_cast<uint8_t(*)[4]>(&temp_number);
            std::swap(number[0], number[3]);
            std::swap(number[1], number[2]);
            return temp_number;
#endif
        }

        static FORCE_INLINE uint32_t fmix32(uint32_t h) {
            h ^= h >> 16;
            h *= 0x85ebca6b;
            h ^= h >> 13;
            h *= 0xc2b2ae35;
            h ^= h >> 16;

            return h;
        }

    public:
        string_view::size_type
        operator()(const string_view &str) const {
            const size_t len = str.length();
            const uint8_t *data = reinterpret_cast<const uint8_t *>(str.data());
            const int nblocks = static_cast<int>(len / 4);

            uint32_t h1 = 0; // seed

            const uint32_t c1 = 0xcc9e2d51U;
            const uint32_t c2 = 0x1b873593U;

            const uint32_t *blocks = reinterpret_cast<const uint32_t *>(data +
                                                                        nblocks * 4);

            for (auto i = -nblocks; i; ++i) {
                uint32_t k1 = Getblock(blocks, i);

                k1 *= c1;
                k1 = Rotl32(k1, 15);
                k1 *= c2;

                h1 ^= k1;
                h1 = Rotl32(h1, 13);
                h1 = h1 * 5 + 0xe6546b64;
            }

            const uint8_t *tail = data + nblocks * 4;

            uint32_t k1 = 0;

            switch (len & 3) {
                case 3:
                    k1 ^= tail[2] << 16;
                case 2:
                    k1 ^= tail[1] << 8;
                case 1:
                    k1 ^= tail[0];
                    k1 *= c1;
                    k1 = Rotl32(k1, 15);
                    k1 *= c2;
                    h1 ^= k1;
                default:
                    break;
            }

            h1 ^= len;

            h1 = fmix32(h1);
            return hash<int>()(h1);
        }

#undef FORCE_INLINE
    };
}

#endif